#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
#define N 30
typedef struct
{
    char *value; //节点值
    int weight;  //权重
    int parent;  //父节点
    int left;
    int right;
} HTNode;

typedef struct
{
    char Code[15]; //用于存放当前节点的哈夫曼编码
    int start;     //表示start~n为哈夫曼编码
} HfmCode;

void CreateHTree(HTNode ht[], int n)
{
    int i, k, lnode, rnode;
    int first_min, second_min;
    for (i = 0; i < 2 * n - 1; i++)
    {
        ht[i].parent = -1;
        ht[i].left = -1;
        ht[i].right = -1;
    }
    for (i = n; i < 2 * n - 1; i++)
    {
        first_min = second_min = 32767;
        lnode = rnode = -1;
        for (k = 0; k < i; k++) //在前i个元素中找两个最小的数
        {
            if (ht[k].parent == -1) //根节点表示没有使用过的节点
            {
                if (ht[k].weight < first_min) //小于最小的权,第一小的变为第二小，ht[k]变为最小
                {
                    second_min = first_min;
                    rnode = lnode;
                    first_min = ht[k].weight;
                    lnode = k;
                }
                else if (ht[k].weight < second_min) //小于第二小，此时ht[k]变为第二小的
                {
                    second_min = ht[k].weight;
                    rnode = k;
                }
            }
        }
        ht[i].weight = ht[lnode].weight + ht[rnode].weight;
        ht[i].left = lnode;
        ht[i].right = rnode;
        ht[lnode].parent = i;
        ht[rnode].parent = i;
    }
}

void CreateHcode(HTNode ht[], HfmCode hcd[], int n)
{
    int i, fu, current;
    HfmCode hc;
    for (i = 0; i < n; i++)
    {
        hc.start = n;
        current = i;
        fu = ht[i].parent;
        while (fu != -1)
        {
            if (ht[fu].left == current) //判断当前节点为父节点的的左孩子还是右孩子
                hc.Code[hc.start--] = '0';
            else
                hc.Code[hc.start--] = '1';
            current = fu;
            fu = ht[fu].parent;
        }
        hc.start++;
        hcd[i] = hc;
    }
}

int main(void)
{
    char words[15][15] = {"The", "of", "a", "to", "and", "in", "that", "he", "is", "at", "on", "for", "His", "are", "be"};
    int frequen[15] = {1192, 677, 541, 518, 462, 450, 242, 195, 190, 181, 174, 157, 138, 124, 123};

    HTNode ht[29];
    for (int i = 0; i < 15; i++)
    {
        ht[i].value = words[i];
        ht[i].weight = frequen[i];
    }
    CreateHTree(ht, 15);
    HfmCode hcd[15];
    CreateHcode(ht, hcd, 15);
    for (int i = 0; i < 15; i++)
    {
        printf("%s的编码为:", ht[i].value);
        for (int j = hcd[i].start; j <= 15; j++)
        {
            printf("%c", hcd[i].Code[j]);
        }
        printf("\n");
    }

    //求平均查找长度
    double sum = 0;
    for (int i = 0; i < 15; i++)
        sum += frequen[i];
    double avgfind_len;
    for (int i = 0; i < 15; i++)
    {
        avgfind_len += (15 - hcd[i].start + 1) * (frequen[i] / sum);
    }
    printf("平均查找长度为：%lf", avgfind_len);
}
